//时间复杂度：并不是具体的执行时间，而是语句执行的次数。

/*
for(int i=1;i<=n;i++)   频度为n+1
{
    for(int j=1;j<=n;j++)   频度为n*(n+1)
    {
        c[i][j] = 0;    频度为n*n
        for(int k=1;k<=n;k++)   频度为n*n*(n+1)
        {
            c[i][j] = c[i][j] + a[i][k] * b[k][j];  频度为n*n*n
        }
    }
}

f(n) = (n+1) + n*(n+1) + n*n + n*n*(n+1) + n*n*n
f(n) = 2n^3 + 3n^2 + 2n + 1

忽略所有低次幂和最高次幂的系数
T(n) = O(n^3)
*/

/*
最好时间复杂度：最短情况
最坏时间复杂度：最慢情况
平均时间复杂度：平均情况
*/

/*
例1：
for(int i=0;i<100000;i++)
{
    x++;
    s=s+i;
}
T(n) = O(1)
如果算法执行时间不随问题规模n的增加而增加，则算法的时间复杂度为O(1)。
（n为常数）

例2：
for(int i=0;i<n;i++)
{
    x++;
    s=s+i;
}
T(n) = O(n)

例3：
for(int i=0;i<n;i++)
{
    x++;
    s=s+i;
}
for(int i=0;i<n;i++)
{
    for(int j=0;j<n;j++)
    {
        x++;
    }
}
T(n) = O(n^2)

例4：
for(int i=0;i<n;i++)    频度为n
{
    for(int j=0;j<i;j++)    频度为n*(n+1)/2
    {
        for(int k=0;k<j;k++))   频度为n*(n+1)*(n+2)/6
        {
            x++;
        }
    }
}
T(n) = O(n^3)

例5：
for(int i=1;i<=n;i=i*2)
{
    x++;
}
T(n) = O(logn)  以2为底
*/

//空间复杂度：除了用来存储代码和输入数据的内存空间外，还需要额外的空间

#include <stdio.h>
int main()
{
    int n=10;
    int c[20][20];
}
